package org.lintcode_Pattern;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-22:48
 * @Description:
 * 使用条件
 * • 用非递归的方式（Non-recursion / Iteration）实现二叉树的中序遍历
 * • 常用于 BST 但不仅仅可以用于 BST
 * 复杂度
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 * 炼码例题
 * • LintCode 67. 二叉树的中序遍历
 * • LintCode 902. 二叉搜索树的第 k 大元素
 * @version: 1.0
 */
public class A5二叉搜索树非递归BST {

	static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 这段代码首先检查根节点是否为空，然后使用一个栈来辅助实现非递归的中序遍历。
	 * 它不断地将当前节点的左子节点压入栈中，直到找到最左的节点。
	 * 然后，它开始弹出栈中的节点，将其值添加到结果列表中，并更新当前节点为弹出节点的右子节点，继续遍历。这个过程重复，直到栈为空且当前节点为null。
	 */
	public static class BinaryTree {

		// 中序遍历二叉树
		public List<Integer> inorderTraversal(TreeNode root) {
			List<Integer> inorder = new ArrayList<>();
			if (root == null) {
				return inorder;
			}

			Stack<TreeNode> stack = new Stack<>();
			TreeNode current = root;

			while (current != null || !stack.isEmpty()) {
				// 遍历到最左的节点
				while (current != null) {
					stack.push(current);
					current = current.left;
				}
				// 弹出栈顶元素，并将其右子节点作为新的当前节点
				current = stack.pop();
				inorder.add(current.val); // 加入中序遍历结果列表
				current = current.right; // 继续遍历右子树
			}

			return inorder;
		}

		public static void main(String[] args) {
			TreeNode root = new TreeNode(1);
			root.left = new TreeNode(2);
			root.right = new TreeNode(3);
			root.left.left = new TreeNode(4);
			root.left.right = new TreeNode(5);

			BinaryTree binaryTree = new BinaryTree();
			List<Integer> result = binaryTree.inorderTraversal(root);
			System.out.println(result); // 输出应为 [4, 2, 5, 1, 3]
		}
	}
}
